class BPlusTreeNode:
    """
    BPlusTreeNode represents a node in a B+ Tree.

    Attributes:
        is_leaf: Flag indicating if the node is a leaf node.
        keys: List of keys stored in the node.
        children: List of child nodes.
        next_leaf: Reference to the next leaf node (for linked list).
    """

    def __init__(self, is_leaf=False):
        """
        Initialize a BPlusTreeNode.

        Args:
            is_leaf: Flag indicating if the node is a leaf node. Defaults to False.
        """
        self.is_leaf = is_leaf
        self.keys = []
        self.children = []
        self.next_leaf = None

    def is_full(self):
        """
        Check if the node is full.

        Returns:
            True if the node is full, False otherwise.
        """
        return len(self.keys) == self.get_max_keys()

    def get_max_keys(self):
        """
        Get the maximum number of keys that the node can hold.

        Returns:
            Maximum number of keys.
        """
        # The maximum number of keys is (order - 1) for internal nodes
        # and order for leaf nodes, where order is the B+ Tree order.
        if self.is_leaf:
            return BPlusTree.order
        else:
            return BPlusTree.order - 1

    def __repr__(self):
        """
        Returns a string representation of the BPlusTreeNode.

        Returns:
            String representation of the BPlusTreeNode.
        """
        return f"Node({self.keys}, {self.is_leaf})"


class BPlusTree:
    """
    BPlusTree represents a B+ Tree data structure.

    Attributes:
        root: Root node of the tree.
        order: Order of the tree.
    """

    order = 3

    def __init__(self):
        """
        Initialize an empty B+ Tree with no root node.
        """
        self.root = None

    def search(self, key):
        """
        Search for a key in the B+ Tree.

        Args:
            key: Key to be searched.

        Returns:
            True if the key is found, False otherwise.
        """
        return self._search_helper(self.root, key)

    def _search_helper(self, node, key):
        """
        Helper method to search for a key in the B+ Tree.

        Args:
            node: Current node being visited.
            key: Key to be searched.

        Returns:
            True if the key is found, False otherwise.
        """
        if node is None:
            return False

        if node.is_leaf:
            # Search for the key in the leaf node
            return key in node.keys

        child_index = self._get_child_index(node, key)
        if child_index >= len(node.children):
            return False

        child = node.children[child_index]
        return self._search_helper(child, key)


    def insert(self, key):
        """
        Insert a key into the B+ Tree.

        Args:
            key: Key to be inserted.
        """
        if self.root is None:
            # Tree is empty, create a new root node
            self.root = BPlusTreeNode(is_leaf=True)
            self.root.keys.append(key)
        else:
            if self.root.is_full():
                # Root node is full, split the root
                old_root = self.root
                self.root = BPlusTreeNode()
                self.root.children.append(old_root)
                self._split_child(self.root, 0)

            self._insert_non_full(self.root, key)

    def _insert_non_full(self, node, key):
        """
        Helper method to insert a key into a non-full node.

        Args:
            node: Current node being visited.
            key: Key to be inserted.
        """
        if node.is_leaf:
            # Insert the key into the leaf node in sorted order
            i = len(node.keys) - 1
            while i >= 0 and key < node.keys[i]:
                i -= 1
            node.keys.insert(i + 1, key)
        else:
            # Find the appropriate child to insert the key
            child_index = self._get_child_index(node, key)
            child = node.children[child_index]
            if child.is_full():
                # Child node is full, split the child
                self._split_child(node, child_index)
                if key > node.keys[child_index]:
                    child_index += 1

            self._insert_non_full(node.children[child_index], key)

    def _split_child(self, parent, child_index):
        """
        Split a full child node into two nodes.

        Args:
            parent: Parent node of the child node.
            child_index: Index of the child node in the parent's children list.
        """
        child = parent.children[child_index]
        new_child = BPlusTreeNode(is_leaf=child.is_leaf)

        # Move the second half of keys and children to the new child node
        mid = child.get_max_keys() // 2
        new_child.keys = child.keys[mid:]
        child.keys = child.keys[:mid]

        if not child.is_leaf:
            new_child.children = child.children[mid:]
            child.children = child.children[:mid]

        # Insert the new child into the parent node
        parent.keys.insert(child_index, new_child.keys[0])
        parent.children.insert(child_index + 1, new_child)

    def _get_child_index(self, node, key):
        """
        Get the index of the child node that should contain the key.

        Args:
            node: Parent node.
            key: Key to be inserted or searched.

        Returns:
            Index of the appropriate child node.
        """
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        return i

    def display(self):
        """
        Display the B+ Tree in a structured format.
        """
        if self.root is None:
            print("Empty B+ Tree")
        else:
            self._display_helper(self.root, "")

    def _display_helper(self, node, indent):
        """
        Helper method to display the B+ Tree in a structured format.

        Args:
            node: Current node being visited.
            indent: Indentation for the current node.
        """
        print(indent, end="")
        print(node)

        if not node.is_leaf:
            for child in node.children:
                self._display_helper(child, indent + "\t")

    def __repr__(self):
        """
        Returns a string that represents a valid Python expression that could be used to recreate the B+ Tree.

        Returns:
            A string that represents a valid Python expression.
        """
        if self.root is None:
            return "Empty B+ Tree"
        return f"BPlusTree(root={self.root.keys})"


if __name__ == "__main__":
    # Create a new B+ Tree
    b_plus_tree = BPlusTree()

    # Insert keys into the B+ Tree
    keys = [6, 4, 9, 1, 7, 12, 3, 5, 8, 10, 14, 2, 11, 13]
    for key in keys:
        b_plus_tree.insert(key)

    # Display the B+ Tree structure
    print("B+ Tree structure:")
    b_plus_tree.display()
    # Output:
    # B+ Tree structure:
    # Node(keys = [6], is_leaf = False)
    # 	Node(keys = [4], is_leaf = False)
    # 		Node(keys = [1, 3], is_leaf = True)
    # 		Node(keys = [4, 5], is_leaf = True)
    # 	Node(keys = [7, 9], is_leaf = False)
    # 		Node(keys = [6, 7], is_leaf = True)
    # 		Node(keys = [8], is_leaf = False)
    # 			Node(keys = [8], is_leaf = True)
    # 			Node(keys = [9, 10, 12], is_leaf = True)
    # 	Node(keys = [11, 13], is_leaf = False)
    # 		Node(keys = [11], is_leaf = False)
    # 			Node(keys = [10], is_leaf = False)
    # 				Node(keys = [9], is_leaf = True)
    # 				Node(keys = [10], is_leaf = True)
    # 			Node(keys = [11], is_leaf = True)
    # 		Node(keys = [12], is_leaf = False)
    # 			Node(keys = [11, 12], is_leaf = True)
    # 			Node(keys = [13, 14], is_leaf = True)

    # Search for a key in the B+ Tree
    key = 8
    is_found = b_plus_tree.search(key)
    print(f"Key {key} is found: {is_found}")
    # Output:
    # Key 8 is found: True
